import java.util.Map;

public class AVLTree {
    /**
     * 平衡二叉树
     */
    public static class Node{
        public int val;
        public int depth;
        public int balance;
        public Node parent;
        public Node left;
        public Node right;

        public Node(int val){
            this.val = val;
            depth = 1;
            balance = 0;
            left = null;
            right = null;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static void insert(Node root, int val){
        if (val < root.val){
            if (root.left != null){
                insert(root.left, val);
            }else {
                root.left = new Node(val);
                root.left.parent = root;
            }
        }else {
            if (root.right != null){
                insert(root.right, val);
            }else {
                root.right = new Node(val);
                root.right.parent = root;
            }
        }
        root.balance = calBalance(root);
        if (root.balance >= 2){
            // LR
            if (root.left.balance == -1){
                left_rotate(root.left);
            }
            // RR
            right_rotate(root);
        }
        if (root.balance <= -2){
            // RL
            if (root.right.balance == 1){
                right_rotate(root.right);
            }
            // LL
            left_rotate(root);
        }
        root.balance = calBalance(root);
        root.depth = calDepth(root);
    }

    private static void left_rotate(Node p) {
        Node pParent = p.parent;
        Node pRightSon = p.right;
        Node pLeftGrandSon = pRightSon.left;
        // 右子变父
        pRightSon.parent = pParent;
        if (pParent != null){
            if (p == pParent.right){
                pParent.right = pRightSon;
            }else if (p == pParent.left){
                pParent.left = pRightSon;
            }
        }
        pRightSon.left = p;
        p.parent = pRightSon;
        // 左孙变右孙
        p.right = pLeftGrandSon;
        if (pLeftGrandSon != null){
            pLeftGrandSon.parent = p;
        }
        p.depth = calDepth(p);
        p.balance = calBalance(p);
        pRightSon.depth = calDepth(pRightSon);
        pRightSon.balance = calBalance(pRightSon);
    }

    private static void right_rotate(Node p) {
        Node pParent = p.parent;
        Node pLeftSon = p.left;
        Node pRightGrandSon = pLeftSon.right;
        // 左子变父
        pLeftSon.parent = pParent;
        if (pParent != null){
            if (p == pParent.left){
                pParent.left = pLeftSon;
            }else if (p == pParent.right){
                pParent.right = pLeftSon;
            }
        }
        pLeftSon.right = p;
        p.parent = pLeftSon;
        // 左孙变右孙
        p.left = pRightGrandSon;
        if (pRightGrandSon != null){
            pRightGrandSon.parent = p;
        }
        p.depth = calDepth(p);
        p.balance = calBalance(p);
        pLeftSon.depth = calDepth(pLeftSon);
        pLeftSon.balance = calBalance(pLeftSon);
    }

    private static int calDepth(Node p) {
        int depth = 0;
        if (p.left !=null){
            depth = p.left.depth;
        }
        if (p.right != null && depth < p.right.depth){
            depth = p.right.depth;
        }
        depth++;
        return depth;
    }

    private static int calBalance(Node p) {
        int left_depth;
        int right_depth;
        left_depth = p.left == null ? 0 : p.left.depth;
        right_depth = p.right == null ? 0 : p.right.depth;
        return left_depth - right_depth;
    }

    public static void main(String[] args) {
        Node root = new Node(3);
        System.out.println(root);
        int[] node = {2,1,4,5,6,7,10,9,8};
        for (int i : node) {
            insert(root,i);
            while (root.parent != null){
                root = root.parent;
            }
            System.out.println(root);
        }
    }
}
